//使用迭代法实现树的深度遍历
//其实也是探索了递归的实现本质：每一次调用将函数变量，参数和返回地址压入栈，结束函数时弹出

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;


//前序遍历
vector<int> preorderTraversal(TreeNode* root)
{
    vector<int> result;
    if(!root) return result;
    stack<TreeNode*> st;
    st.push(root);
    while(!st.empty())
    {
        TreeNode* node=st.top();
        st.pop();
        result.push_back(node->val);
        if(node->right) st.push(node->right);       //这里有一个易错点，应该先将右孩子入栈，这样才能按中左右的顺序出栈
        if(node->left) st.push(node->left);     
    }

    return result;

}

//后序遍历
//后序遍历的结构和前序遍历相似
//要采用左右中的顺序，可以先调整前序遍历的顺序为中右左，如何将结果数组翻转，就得到了左右中的顺序！
vector<int> postorderTraversal(TreeNode* root)
{
    vector<int> result;
    if(!root) return result;
    stack<TreeNode*> st;
    st.push(root);
    while(!st.empty())
    {
        TreeNode* node=st.top();
        st.pop();
        result.push_back(node->val);
        if(node->left) st.push(node->left);
        if(node->right) st.push(node->right);   //先入栈左孩子，实现中右左的顺序
    }
    reverse(result.begin(),result.end());       //反转数组，reverse包含在头文件algorithm中
    return result;
}



//中序遍历，跟前序和后序有点不同
//访问中间结点后要跳转到右孩子，如何继续进行中序遍历
vector<int> inorderTraversal(TreeNode* root)
{
    vector<int> result;
    if(!root) return result;
    stack<TreeNode*> st;
    TreeNode* cur=root;
    while(cur!=nullptr||!st.empty())
    {
        //先往左走到头
        if(cur)
        {
            st.push(cur);
            cur=cur->left;
        }
        else    //到最左结点
        {
            cur=st.top();
            st.pop();
            result.push_back(cur->val);
            cur=cur->right; //cur跳转到右结点，然后按照先走到左尽头再访问左中的顺序继续
            //不是将cur->right入栈！！！
        }
    }
    return result;
}